package com.maven.sort;

import java.util.Arrays;

/**
 * 合并排序
 * <p>
 * 小和问题
 * 求每一个数右边有多少比他大(小)
 *
 * @Author YongQiang
 * @Date 2021/8/11 12:07
 * @Version 1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {12, 45, 34, 24, 85, 5, 31, 45, 76, 5, 17, 75, 28};
        //swap(arr, 2, 3);
        fuMergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void fuMergeSort(int[] arr, int L, int R) {
        if (arr.length <= 1 || L == R) {
            return;
        }
        // >> 优先级低于+，此处一定要带括号
        int mid = L + ((R - L) >> 1);
        fuMergeSort(arr, L, mid);
        fuMergeSort(arr, mid + 1, R);
        merge(arr, L, mid, R);

    }

    public static void merge(int[] arr, int L, int mid, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int leftIndex = L;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= R) {
            help[i++] = arr[leftIndex] < arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];
        }
        while (leftIndex <= mid) {
            help[i++] = arr[leftIndex++];
        }
        while (rightIndex <= R) {
            help[i++] = arr[rightIndex++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

    public static void swap(int[] arr, int a, int b) {
        if (a == b) {
            return;
        }
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }
}
